\section{Счетные множества}

\subsection*{29}

Рассмотрим \[\pi: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}:
\langle n_1,n_2 \rangle \mapsto \dfrac{(n_1 + n_2)(n_1 + n_2 + 1)}{2} + n_2\]

1) Докажем, что $\pi(n_1,n_2)$ инъективно:

Предположим, что существуют $m,n,p,q: \pi(m,n) = \pi(p,q)$, докажем, что тогда $\langle m,n \rangle = \langle p,q \rangle$.

\begin{equation}
\dfrac{(m + n)(m + n + 1)}{2} + n = \dfrac{(p + q)(p + q + 1)}{2} + q
\end{equation}

Для начала покажем, что  $m + n = p + q$. Пусть это не так. Тогда без ограничения общности скажем, что $m + n < p + q$. Для удобства обозначим $a = m + n$ и $d = (p + q) - a$, из чего следует
\[\dfrac{a(a+1)}{2} + n = \frac{(a + d)(a + d + 1)}{2} + q\]
Тогда
\[n - q = \dfrac{(a + d)(a + d + 1)}{2} - \dfrac{a(a+1)}{2} = ad + \dfrac{d(d+1)}{2} \geq a+1\]
поэтому $n > a + q \geq a = m + n \geq n$ - противоречие. Значит, $m + n = p + q$, тогда из равенства $(1.1)$ немедленно следует, что $n = q$, из чего не менее стремительно следует $m = p$. Что означает, что $\pi(n_1,n_2)$ - инъективно.\\

\pagebreak

2) Докажем, что $\pi(n_1,n_2)$ сюръективно:

Пусть $z \in \mathbb{Z}: z = \pi(n_1, n_2)$

$\omega = n_1 + n_2$

$t = \dfrac{\omega(\omega + 1)}{2} = \dfrac{\omega^2 + \omega}{2}$

$z = t + n_2$\\

Рассмотрим уравнение верное для любых $n_1, n_2$: \[\omega^2 + \omega - 2t = 0\]

$\omega = \dfrac{\sqrt{8t + 1} - 1}{2}$ - строго возрастает, так как $t \in \mathbb{N}$

\[t \leq z = t + n_2 < t + (\omega + 1) = \dfrac{(\omega + 1)^2 + (\omega + 1)}{2}\]

(Подставим значение $\omega + 1$ в исходный трехчлен)

$\omega \leq \dfrac{\sqrt{8z + 1} - 1}{2} < \omega + 1$

$\omega = \left \lfloor \dfrac{\sqrt{8z + 1} - 1}{2} \right \rfloor$ 

$t = \dfrac{\omega(\omega + 1)}{2} = \dfrac{\omega^2 + \omega}{2}$

$n_2 = z - t$

$n_1 = \omega - n_2$\\

Из чего следует, что для любого образа $z$, существует прообраз $\langle n_1, n_2 \rangle$\\

Значит, $\pi(n_1, n_2)$ - инъективно и сюръективно, следовательно оно биективно \hfill $\blacksquare$

\subsection*{31}

Так как в каждом таком интервале $\exists q$ - рациональная точка, сопоставим каждому интервалу такую точку, составив такую взаимно однозначное соответствие между интервалом и точкой $q$. Значит множество таких интервалов равномощно $\mathbb{Q}$, значит оно не более чем счетно

\subsection*{32}

а) Сопоставим каждой такой "восьмерки" неупорядоченную пару рациональных чисел, описывающих координаты центров каждой из окружностей. Так как "восьмерки" непересекающиеся, значит пары рациональных чисел не могут повторяться. Тем самым количество таких "восьмерок" равномощно $\mathbb{Q}^4$, значит их не более чем счетно\\

б) Для каждой такой буквы "Т" выделим длинну наименьшего отрезка $x$ и сопоставим каждой такой букве вершины равностороннего треугольника, с центром в пересечении отрезков данной буквы и длинной сторон равные $\frac{x}{10}$. Так как буквы "Т" не пересекаются, то данный набор вершин ни у одной из данных букв не может совпадать. Значит множество букв "Т" равномощно $\mathbb{Q}^6$, значит их не более чем счетно

\subsection*{33}

Рассмотрим $x_0$ - точку максимума функции. По определению максимума $\exists \dot{U}(x_0)$ - поколотая окрестность, такая что \[\forall x \in \dot{U}(x_0): f(x) < f(x_0)\] $\implies \exists x_q$ - рациональная точка, такая что $x_q \in \dot{U}(x_0)$

Сопоставим каждому значению максимума такую точку $x_q$, значит множество точек строгого локального максимума равномощно $\mathbb{Q}$, значит их не более чем счетно

\subsection*{34}

Рассмотрим точки разрыва 1-го рода (для 2-го доказательство аналогично). Так как функция неубывающая $\forall x_1, x_2: x_1 < x_2 \implies f(x_1) \leq f(x_2)$.

По определению для $x_0$ - точка разрыва, \[\lim\limits_{x \to x_0-0} f(x) \neq \lim\limits_{x \to x_0+0} f(x)\] и так как функция неубывающаяя, значит $\lim\limits_{x \to x_0-0} f(x) < \lim\limits_{x \to x_0+0} f(x)$

Тогда сопоставим точке $x_0$, рациональную точку $x_q$ из $\dot{U}(x_0)$, находящаяяся левее точки $x_0$. Значит множество точек разрыва равномощно $\mathbb{Q}$, значит оно не более чем счетно

\subsection*{35}

Пусть $A = \{q \in \mathbb{Q} \mid q = 2^{-k}\}$. Тогда $[0;1] = ([0;1) \setminus A) \cup A \cup \{1\}$

Так как объеденение счетного и конечного множеств счетно, то значит $A \cup \{1\}$ равномощно $A$. Из чего следует, что $([0;1) \setminus A) \cup A \cup \{1\}$ равномощно $([0;1) \setminus A) \cup A = [0;1)$

\subsection*{36}

Пусть $A$ - континуально, $B$ - счетно. Нужно доказать, что $A \setminus B$ равномощно $A$.

Рассмотрим $C \subset A: C$ - счетно, $C = D + E$, при $D, E$ - счетные. Так как $E$ и $B$ - счетны, то значит они равномощны, тем самым $A = (A \setminus C) \cup C =  (A \setminus C) \cup D \cup E$ равномощно $(A \setminus C) \cup D \cup B$, при этом объеденение счетных множеств счетно, а значит оно равномощно $(A \setminus C) \cup D = A \setminus B$

\subsection*{37}

От противного, пусть $\exists A: A$ - конечно, $\exists B \subsetneq A: A$ равномощно $B$

По условию $B \subsetneq A \implies \exists a_0: a_0 \in A$ и $a \notin B$. Так как по условию они равномощны, значит $\exists \varphi: A \rightarrow B$ - биективная, тогда каждому $a \in A$ соответствует $\varphi(a) \in B$, но по принципу Дирихле, так как каждому $b \in B$ соответствует $\varphi^{-1}(b) \in A$, то $\nexists \varphi(a_0) \in B$, так как иначе одному элементу из $B$ соответствовало бы несколько элементов из $A$ - противоречие

\subsection*{38}

Рассмотрим $\varphi : [0;1] \rightarrow [0;1] \cup [2;3] \cup ...$. Пусть для любого $k \in \mathbb{N}$ $\varphi:$ \[\left[\dfrac{1}{2^{k+1}}; \dfrac{1}{2^{k}}\right] \rightarrow [2k; 2k+1]\] И так как $\bigcup\limits_{k \in \mathbb{N}} \left[\dfrac{1}{2^{k+1}}; \dfrac{1}{2^k}\right] = [0;1]$, значит $\varphi$ задает взаимно однозначное соответствие между $[0;1]$ и $[0;1] \cup [2;3] \cup ...$

\subsection*{39}

Рассмотрим два случая:

1) Прямые непараллельные $Ox:$

Всякая такая прямая задается $\langle \varphi, r \rangle$, $\varphi$ - под каким углом пересекает прямая $Ox$ и $r$ - расстояние до точки пересечения, значит мы сопоставляем каждой такой прямой $\langle x, y \rangle$, при $x \neq 0$\\

2) Прямые параллельные $Ox:$

Всякая такая прямая задается 1 числом - расстоянием от данной прямой до $Ox$. Сопоставим такой прямой точки плоскости $\langle 0, y \rangle$\\

Таким образом мы сопоставили всякой прямой в плоскости некоторую точку

\subsection*{40}

Рассмотрим функцию $\varphi: \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}_+ \times \mathbb{R}$. Допустим $\varphi: \langle x; y \rangle \rightarrow \langle e^x; y \rangle$. Тем самым мы сопоставляем каждой точке плоскости точку из полуплоскости и наоборот, значит полуплоскоть равномощна всей плоскости

\subsection*{41}

\[\dfrac{1}{3}_{10} = \dfrac{1}{11}_2 = 0,(01)_2\]

\subsection*{42 $\filledstar$}

Представим все последовательности длинны $N$ в виде $N$-мерного пространства $\sim \mathbb{R}^N$, и каждой последовательности сопоставим какую-то точку из $\mathbb{R}^N$, которая как раз таки описывается последовательностью $\langle x_1, x_2, ..., x_n \rangle$ длинны $N$. Тем самым множество всех последовательностей длинны $N$ равномощно $\mathbb{R}^N$

Рассмотрим множество всех последовательностей действительных чисел: по вышедоказанному оно равномощно $\bigcup\limits_{n \in \mathbb{N}} \mathbb{R}^n$, и так как $\forall n, \mathbb{R}^n$ - равномощно $\mathbb{R}$, то значит $\bigcup\limits_{n \in \mathbb{N}} \mathbb{R}^n$ равномощно $\mathbb{R}$, значит множество всех конечных последовательностей действительных чисел равномощно $\mathbb{R}$


\subsection*{43}

Лемма: Множество знаков после запятой у всякого числа не более чем счетно. Доказательство очевидно, просто сопоставляем каждому знаку его порядковый номер\\

Рассмотрим "бесконечномерное пространство" $\sim \mathbb{R}^\mathbb{N}$ и каждой точке пространства сопоставим ее координаты $\langle x_1, x_2, ... \rangle$

Так как $\mathbb{R}^\mathbb{N}$ - равномощно "бесконечномерному единичному кубу", то рассмотрим двоичную записть координат каждой точки данного куба

\begin{align*}
x_1 &\sim 0,y_1^1y_2^1y_3^1..._{(2)}\\
x_2 &\sim 0,y_1^2y_2^2y_3^2..._{(2)}\\
x_3 &\sim 0,y_1^3y_2^3y_3^3..._{(2)}\\
\vdots
\end{align*}

И так как согласно лемме количество знаков после запятой не более чем счетно, то объеденение счетного количества счетных множеств - счетно, значит мы всякой точке из "бесконечномерного куба" можем сопоставить точку из отрезка. Тем самым мы постоили инъекцию в $\mathbb{R}$, а так как очевидно $\mathbb{R} \subseteq \mathbb{R}^\mathbb{N}$, то значит $\mathbb{R}$ и $\mathbb{R}^\mathbb{N}$ - равномощны 




 